﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TerrainGenerator
{
    class VarianceTree
    {
        public float[,] Heightmap { get { return heightmap; } }
        public float[] Tree { get { return variancetree; } }
        public Triangle[] Triangles { get { return triangles; } }
        
        float[,] heightmap;
        float[] variancetree;
        Triangle[] triangles;

        public VarianceTree(float[,] heightmap)
        {
            this.heightmap = heightmap;
            int width = heightmap.GetLength(0) - 1;
            int height = heightmap.GetLength(1) - 1;
            int arraySize = 4 * width * height - 1;
            variancetree = new float[arraySize];
            triangles = new Triangle[arraySize];

            Triangle leftRoot = new Triangle(1, 0, height, 0, 0, width, 0);
            Triangle rightRoot = new Triangle(2, width, 0, width, height, 0, height);

            CalcVariance(leftRoot);
            CalcVariance(rightRoot);
        }

        void CalcVariance(Triangle triangle)
        {
            float variance = triangle.Variance(heightmap);
            if (!triangle.IsLeaf())
            {
                Triangle leftChild = triangle.LeftChild();
                CalcVariance(leftChild);
                if (variancetree[leftChild.Index] > variance)
                {
                    variance = variancetree[leftChild.Index];
                }
                Triangle rightChild = triangle.RightChild();
                CalcVariance(rightChild);
                if (variancetree[rightChild.Index] > variance)
                {
                    variance = variancetree[rightChild.Index];
                }
            }
            variancetree[triangle.Index] = variance;
            triangles[triangle.Index] = triangle;
        }

        public int ParentIndex(int index)
        {
            return (index + 1) / 2;
        }

        public int LeftChildIndex(int index)
        {
            return index * 2 + 1;
        }

        public int RightChildIndex(int index)
        {
            return index * 2 + 2;
        }
    }
}
